package map_1113;


public class BSTreeMap {
    private TreeNode root;
    private int size;

    public BSTreeMap() {
        this.root = null;
        this.size = 0;
    }

    public String put(Long key, String value) {
        // 1. 插入  搜索树中没有这个 key 时，返回 null
        // 2. 更新  搜索树中有这个 key 时，返回原来的 value

        if(root==null){
            root=new TreeNode(key,value);
            this.size=1;
            return null;
        }

        TreeNode parent=null;
        TreeNode cur=root;
        int c=-1;
        while(cur!=null){
            c=key.compareTo(cur.key);
            if(c==0){
                String oldValue= cur.value;
                cur.value=value;
                return oldValue;
            }else if(c<0){
                parent=cur;
                cur=cur.left;
            }else{
                parent=cur;
                cur=cur.right;
            }
        }
        TreeNode node=new TreeNode(key,value);
        if(c<0){
            parent.left=node;
        }else{
            parent.right=node;
        }
        size++;
        return null;


//        if (root == null) {
//            root = new TreeNode(key, value);
//            this.size = 1;
//            return null;
//        }
//
//        TreeNode parent = null;
//        TreeNode cur = root;
//        int c = -1;
//        while (cur != null) {
//            c = key.compareTo(cur.key);
//            if (c == 0) {
//                String oldValue = cur.value;
//                cur.value = value;
//                return oldValue;
//            } else if (c < 0) {
//                parent = cur;
//                cur = cur.left;
//            } else {
//                parent = cur;
//                cur = cur.right;
//            }
//        }
//
//        TreeNode node = new TreeNode(key, value);
//        if (c < 0) {
//            parent.left = node;
//        } else {
//            parent.right = node;
//        }
//        size++;
//
//        return null;
    }

    public String get(Long key) {
        TreeNode cur = root;
        while (cur != null) {
            int c = key.compareTo(cur.key);
            if (c == 0) {
                return cur.value;
            } else if (c < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        BSTreeMap map = new BSTreeMap();
        map.put(1L, "一");
        map.put(2L, "二");
        map.put(30L, "三十");

        System.out.println(map.get(1L));
    }
}
